Longest Increasing Subsequence Algorithm
The Longest Increasing Subsequence (LIS) Algorithm is a classic dynamic programming problem that aims to find the longest subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique. The algorithm has applications in various fields such as data analysis, genomics, and machine learning, where finding the longest ordered subsequence amidst disorder is crucial.
There are several approaches to solving the LIS problem, such as dynamic programming, binary search, and segment trees. The dynamic programming approach involves creating an auxiliary table that stores the length of the longest increasing subsequence ending at each element in the given sequence. The algorithm iterates through the input sequence and fills the auxiliary table by comparing each element with its preceding elements. The final solution can be obtained by finding the maximum value in the auxiliary table. This approach has a time complexity of O(n^2), where n is the length of the input sequence. Alternatively, more efficient algorithms based on binary search or segment trees can achieve a time complexity of O(n*log(n)).
//Program to calculate length of longest increasing subsequence in an array
#include <bits/stdc++.h>
using namespace std;
int LIS(int a[], int n)
{
int lis[n];
for (int i = 0; i < n; ++i)
{
lis[i] = 1;
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < i; ++j)
{
if (a[i] > a[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
}
}
int res = 0;
for (int i = 0; i < n; ++i)
{
res = max(res, lis[i]);
}
return res;
}
int main(int argc, char const *argv[])
{
int n;
cout << "Enter size of array: ";
cin >> n;
int a[n];
cout << "Enter array elements: ";
for (int i = 0; i < n; ++i)
{
cin >> a[i];
}
cout << LIS(a, n) << endl;
return 0;
}
